import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 判断是否为回文链表
     *
     * @return bool布尔型
     */
    class ListNode {
        int val;
        ListNode next = null;
    }


    public boolean isPalindrome(ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        ListNode curN = cur;
        while (curN != null) {
            if (cur != null) {
                curN = cur.next;
            }
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        ListNode left = head;
        ListNode right = slow;
        while (left != right) {
            if (left.val != right.val) {
                return false;
            }
            if (left.next == right) {
                return true;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }


    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = pRoot;
        queue.offer(pRoot);
        int i = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size != 0) {
                TreeNode top = queue.poll();
                list.get(i).add(top.val);
                if (top.left != null) {
                    queue.offer(top.left);
                }
                if (top.right != null) {
                    queue.offer(top.right);
                }
                size--;
            }
            i++;
        }
        return list;
    }
    public boolean isW(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.offer(root);

        while (cur != null) {
            cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        while (!queue.isEmpty()) {
            TreeNode is = queue.poll();
            if (is != null) {
                return false;
            }
        }
        return true;
    }
}